2910. ABCDEF

Имеется множество S целых чисел от -30000 до 30000 (включительно).

Найти общее количество шестерок (a, b, c, d, e, f) : a, b, c, d, e, f Î S, d ≠ 0, удовлетворяющих равенству:

(a * b + c) / d – e = f

Вход. Первая строка содержит целое число n (1 ≤ n ≤ 100) – размер множества S. Элементы множества S заданы во второй строке. Все числа множества S различны.

Выход. Вывести общее количество искомых шестерок.

Пример входа	Пример выхода
3 5 7 10	10

РЕШЕНИЕ

сортировка

Анализ алгоритма

Перепишем равенство в виде a * b + c = (f + e) * d. Занесем в массив m1 все возможные значения выражения a * b + c (a, b, c Î S). Занесем в массив m2 все возможные значения выражения (f + e) * d (f, e, d Î S). Отсортируем массивы m1 и m2. Найдем общие числа в двух массивах. Пусть число x содержится в m1 p раз, а в m2 q раз. Тогда количество искомых шестерок следует увеличить на p * q.

Реализация алгоритма

В массиве s храним элементы множества S. Объявим массивы m1 и m2. Поскольку имеется не более 100 различных значений для всех переменных, то различных значений a * b + c и (f + e) * d не более 100³.

#define MAX 100

int s[101];

int m1[MAX*MAX*MAX+10], m2[MAX*MAX*MAX+10];

Основная часть программы. Читаем элементы множества S в массив s.

scanf("%d",&n);

for(i = 0; i < n; i++) scanf("%d",&s[i]);

Генерируем все значения выражения a * b + c и заносим их в массив m1. Сортируем их.

for(i = a = 0; a < n; a++)

for(b = 0; b < n; b++)

for(c = 0; c < n; c++)

m1[i++] = s[a] * s[b] + s[c];

sort(m1,m1+i);

Генерируем все значения выражения (f + e) * d и заносим их в массив m2. Помним, что значение d не равно 0. Сортируем их.

for(j = d = 0; d < n; d++)

if (s[d] != 0)

for(e = 0; e < n; e++)

for(f = 0; f < n; f++)

m2[j++] = s[d] * (s[e] + s[f]);

sort(m2,m2+j);

Массив m1 содержит i чисел. Массив m2 содержит j чисел. Индекс pi движется по ячейкам массива m1, индекс pj движется по ячейкам массива m2. За время O(i + j) находим общие числа массивов и количество их вхождений в m1 и m2. Если некоторое число содержится в m1 qi – pi раз, а в m2 qj – pj раз, то количество искомых шестерок res увеличиваем на (qi – pi) * (qj – pj).

for(res = pi = pj = 0; pi < i && pj < j;)

{

if (m1[pi] < m2[pj]) pi++; else

if (m1[pi] > m2[pj]) pj++; else

{

qi = pi; qj = pj;

while((m1[qi] == m1[pi]) && (qi < i)) qi++;

while((m2[qj] == m2[pj]) && (qj < j)) qj++;

res += (qi - pi) * (qj - pj);

if ((qi == i) || (qj == j)) break;

pi = qi; pj = qj;

}

}

Выводим найденное количество шестерок res.

printf("%d\n",res);